// O(1)的时间删除一个链表的节点、
#include <iostream>

struct Node
{
    int _value;
    Node *_next;

    Node(int value) : _value(value), _next(nullptr) {}
};

Node *CreateList1()
{
    Node *node1 = new Node(1);
    Node *node2 = new Node(2);
    Node *node3 = new Node(2);
    Node *node4 = new Node(4);
    Node *node5 = new Node(5);
    Node *node6 = new Node(6);

    node1->_next = node2;
    node2->_next = node3;
    node3->_next = node4;
    node4->_next = node5;
    node5->_next = node6;

    return node1;
}

Node *CreateList2()
{
    Node *node1 = new Node(1);
    Node *node2 = new Node(1);
    Node *node3 = new Node(3);
    Node *node4 = new Node(4);
    Node *node5 = new Node(5);
    Node *node6 = new Node(5);

    node1->_next = node2;
    node2->_next = node3;
    node3->_next = node4;
    node4->_next = node5;
    node5->_next = node6;

    return node1;
}

// 删除节点
void DeleteNode(Node *&head, Node *cur)
{
    if (head == nullptr || cur == nullptr)
        throw std::exception();

    // 如果删除的不是尾部节点
    if (cur->_next != nullptr)
    {
        Node *next_node = cur->_next;
        cur->_value = next_node->_value;
        cur->_next = next_node->_next;
        delete next_node;
        next_node = nullptr;
    }
    // 如果删除的是尾节点,而且也是头节点
    else if (head == cur)
    {
        delete head;
        head = nullptr;
        cur = nullptr;
    }
    // 删除尾节点
    else
    {
        Node *prev_node = head;
        while (prev_node->_next != cur)
        {
            prev_node = prev_node->_next;
        }
        prev_node->_next = nullptr;
        delete cur;
        cur = nullptr;
    }
}

void DeleteRepeatedNode(Node *&head)
{
    if (head == nullptr)
        throw std::exception();
    if (head->_next == nullptr)
        return;

    Node *prev = head;
    Node *cur = head->_next;
    while (cur)
    {
        if (prev->_value == cur->_value)
        {
            Node *next = cur->_next;
            delete cur;
            cur = next;
            prev->_next = cur;
        }
        else
        {
            prev = cur;
            cur = cur->_next;
        }
    }
    while (head != nullptr)
    {
        std::cout << head->_value << " ";
        head = head->_next;
    }
    std::cout << std::endl;
}


int main()
{
    Node *head = CreateList2();
    // Node *head = CreateList1();
    DeleteRepeatedNode(head);

    return 0;
}
